Greedy Alogrithm 1

동적 프로그래밍은 모든 선택을 통해 얻은 결과를 메모함으로서 모든 선택을 고려한다.
Greedy Algorithm은 각 단계에 있어서 가장 좋을 것으로 기대되는 선택을 한다.
-> 전체적으로 최적해로 안내될 것이라는 기대를 가지고 부분적으로 최적인 선택을 함

항상 최적의 해답을 구함을 보장하지 못함
활동 선택 문제(Activity-Selection Problem)
서로 양립할 수 있는 활동들로 이루어진 최대 크기의 부분 집합
선택지 S=a1,a2,a3,...an가 끝나는 시간 ai.f로 정렬되어 있는 경우, 가장 먼저 선택해야 할 활동은 가장 종료 시간이 빠른 a1이다. ak가 종료된 후에 시작하는 활동들의 집합 Sk={ai∈S:si≥fk}
- 재귀 그리디 알고리즘
#include <iostream>
#include <algorithm>
struct Act{
int s, f;
Act(){}
Act(int _s, int _f): s(_s), f(_f) {}
~Act(){}
void set(int _s, int _f){
this->s=_s;
this->f=_f;
}
};
bool ActCmp(Act act1, Act act2){
return act1.f<act2.f;
}
struct Acts{
Act* arr;
int size, cap=0;
Acts(int _size): size(_size) {
this->arr=new Act[this->size];
}
void insert(int _s, int _f){
if(cap==size){
std::cout<<"Acts Full"<<std::endl;
exit(1);
}
arr[cap++].set(_s, _f);
}
void sort(void){
std::sort(arr, arr+size, ActCmp);
}
int s(int ind){
return this->arr[ind].s;
}
int f(int ind){
return this->arr[ind].f;
}
};
struct Array{
int* arr;
int sz, cap=0;
Array(int _sz): sz(_sz) {
arr=new int[sz];
}
void insert(int ind){
this->arr[this->cap++]=ind;
}
void print(void){
for(int i=0; i<this->cap; ++i) std::cout<<arr[i]<<' ';
std::cout<<std::endl;
}
};
void RecursiveActivitySelector(Acts acts, int k, int n, Array& index){
int m=k+1;
while(m<=n && acts.s(m)<acts.f(k)) m=m+1;
if(m<=n) {
index.insert(m+1);
RecursiveActivitySelector(acts, m, n, index);
return;
}
else return;
}
int main(void){
Acts acts(11);
Array index(11);
int s[11]={1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
int f[11]={4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16};
for(int i=0; i<11; ++i) acts.insert(s[i], f[i]);
acts.sort();
RecursiveActivitySelector(acts, -1, 11, index);
index.print();
return 0;
}
위의 재귀함수는 꼬리 재귀(Tail Recursive)이기 떄문에 쉽게 반복 순환형으로 바꿀 수 있다.
반복 순환 그리디 알고리즘
#include <iostream>
#include <algorithm>
struct Act{
int s, f;
Act(){}
Act(int _s, int _f): s(_s), f(_f) {}
~Act(){}
void set(int _s, int _f){
this->s=_s;
this->f=_f;
}
};
bool ActCmp(Act act1, Act act2){
return act1.f<act2.f;
}
struct Acts{
Act* arr;
int size, cap=0;
Acts(int _size): size(_size) {
this->arr=new Act[this->size];
}
void insert(int _s, int _f){
if(cap==size){
std::cout<<"Acts Full"<<std::endl;
exit(1);
}
arr[cap++].set(_s, _f);
}
void sort(void){
std::sort(arr, arr+size, ActCmp);
}
int s(int ind){
return this->arr[ind].s;
}
int f(int ind){
return this->arr[ind].f;
}
};
struct Array{
int* arr;
int sz, cap=0;
Array(int _sz): sz(_sz) {
arr=new int[sz];
}
void insert(int ind){
this->arr[this->cap++]=ind;
}
void print(void){
for(int i=0; i<this->cap; ++i) std::cout<<arr[i]<<' ';
std::cout<<std::endl;
}
};
void GreedyActivitySelector(Acts acts, Array& index){
acts.sort();
int n=acts.size;
int ind=0;
index.insert(ind+1);
int k=1;
for(int m=1; m<n; ++m){
if(acts.s(m)>=acts.f(k)){
index.insert(m+1);
k=m;
}
}
}
int main(void){
Acts acts(11);
Array index(11);
int s[11]={1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12};
int f[11]={4, 5, 6, 7, 9, 9, 10, 11, 12, 14, 16};
for(int i=0; i<11; ++i) acts.insert(s[i], f[i]);
acts.sort();
GreedyActivitySelector(acts, index);
index.print();
return 0;
}